Pisano period

 ( Fibonacci Numbers ) 

In number theory, the nth Pisano period, written as ( n), is the period with which the sequence of taken modulo n repeats. Pisano periods are named after Leonardo Pisano, better known as Fibonacci. The existence of periodic functions in Fibonacci numbers was noted by Joseph Louis Lagrange in 1774. On Arithmetical functions related to the Fibonacci numbers. Acta Arithmetica XVI (1969). Retrieved 22 September 2011.

---

Definition The Fibonacci numbers are the numbers in the integer sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, ...

defined by the recurrence relation

$F\_0\; =\; 0$

$F\_1\; =\; 1$

$F\_i\; =\; F\_\{i-1\}\; +\; F\_\{i-2\}.$

For any integer n, the sequence of Fibonacci numbers F_i taken modulo n is periodic. The Pisano period, denoted ( n), is the length of the period of this sequence. For example, the sequence of Fibonacci numbers modulo 3 begins:

0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, ...

This sequence has period 8, so (3) = 8.

---

Properties

---

Parity With the exception of (2) = 3, the Pisano period ( n) is always even.

This follows by observing that ( n) is equal to the order of the Fibonacci matrix

$$

\mathbf Q = \begin{bmatrix} 1 & 1\\1 & 0 \end{bmatrix} in the general linear group $\backslash text\{GL\}\_2(\backslash mathbb\{Z\}\_n)$of invertible 2 by 2 matrices in the finite ring $\backslash mathbb\{Z\}\_n$of integers modulo n. Since Q has determinant −1, the determinant of Q ^{( n)} is (−1)^{( n)}, which is equal to 1 when either n ≤ 2 or ( n) is even. A Theorem on Modular Fibonacci Periodicity. Theorem of the Day (2015). Retrieved 7 January 2016.

---

Pisano periods of composite numbers If m and n are coprime, then ( mn) is the least common multiple of ( m) and ( n). This follows from Chinese remainder theorem.

Thus the Pisano periods of composite numbers can be computed by looking at the Pisano periods q =  p ^k, for k ≥ 1.

If p is Prime number, ( p ^k) divides p ^k–1 ( p). It is unknown if $\backslash pi(p^k)\; =\; p^\{k-1\}\backslash pi(p)$ for every prime p and integer k > 1. Any prime p providing a counterexample would necessarily be a Wall–Sun–Sun prime, and conversely every Wall–Sun–Sun prime p gives a counterexample (set k = 2).

For p = 2 and 5, the exact values of the Pisano periods are known. The periods of powers of these prime powers are as follows:

• If n = 2 ^k, then $\backslash pi(n)\; =\; 3\; \backslash cdot\; 2^\{k-1\}\; =\; \backslash frac\{3n\}2$
• if n = 5 ^k, then $\backslash pi(n)\; =\; 4\; \backslash cdot\; 5^k\; =\; 4n$

From these it follows that if n = 2·5 ^k then ( n) = 6 n.

---

Pisano periods of prime numbers If prime p is different from 2 and 5, then ( p) is a divisor of p² − 1. This follows from the modulo p analogue of Binet's formula, which implies that ( p) is the multiplicative order of a root of modulo p.

Every p other than 2 and 5 lie in the residue classes $p\; \backslash equiv\; \backslash pm\; 1\backslash \; (\backslash mathrm\{mod\}\backslash \; 10)$ or $p\; \backslash equiv\; \backslash pm\; 3\backslash \; (\backslash mathrm\{mod\}\backslash \; 10)$.

• If $p\; \backslash equiv\; \backslash pm\; 1\backslash \; (\backslash mathrm\{mod\}\backslash \; 10)$, then ( p) divides p − 1.

• If $p\; \backslash equiv\; \backslash pm\; 3\backslash \; (\backslash mathrm\{mod\}\backslash \; 10)$, then ( p) divides 2( p + 1).

The former can be proven by observing that if $p\; \backslash equiv\; \backslash pm\; 1\backslash \; (\backslash mathrm\{mod\}\backslash \; 10)$, then the roots of modulo p belong to $\backslash mathbb\{F\}\_\{p\}\; =\; \backslash mathbb\{Z\}/p\backslash mathbb\{Z\}$ (by quadratic reciprocity). Thus their order, ( p) is a divisor of p − 1.

To prove the latter, if $p\; \backslash equiv\; \backslash pm\; 3\backslash \; (\backslash mathrm\{mod\}\backslash \; 10),$ the roots modulo p of do not belong to $\backslash mathbb\{F\}\_\{p\}$ (by quadratic reciprocity again), and belong to the finite field $\backslash mathbb\{F\}\_\{p\}x/(x^2\; -\; x\; -\; 1).$ As the Frobenius automorphism $x\; \backslash mapsto\; x^p$ exchanges these roots, it follows that, denoting them by r and s, we have r^p = s, and thus r^p+1 = –1. That is r^{2( p+1)} = 1, and the Pisano period, which is the order of r, is the quotient of 2( p + 1) by an odd divisor.

It follows from above results, that if n = p ^k is an odd prime power such that ( n) > n, then ( n)/4 is an integer that is not greater than n. The multiplicative property of Pisano periods imply thus that

( n) ≤ 6 n, with equality if and only if n = 2 · 5 ^r, for r ≥ 1.

If n is not of the form 2 · 5 ^r, then ( n) ≤ 4 n.

---

Tables The first twelve Pisano periods and their cycles (with spaces before the zeros for readability) are Graph of the cycles modulo 1 to 24. Each row of the image represents a different modulo base n, from 1 at the bottom to 24 at the top. The columns represent the Fibonacci numbers mod n, from F(0) mod n at the left to F(59) mod n on the right. In each cell, the brightness indicates the value of the residual, from dark for 0 to near-white for n−1. Blue squares on the left represent the first period; the number of blue squares is the Pisano number. (using X and E for ten and eleven, respectively):

The first 144 Pisano periods are shown in the following table:

---

Pisano periods of Fibonacci numbers If n = F(2 k) ( k ≥ 2), then π( n) = 4 k; if n = F(2 k + 1) ( k ≥ 2), then π( n) = 8 k + 4. That is, if the modulo base is a Fibonacci number (≥ 3) with an even index, the period is twice the index and the cycle has two zeros. If the base is a Fibonacci number (≥ 5) with an odd index, the period is four times the index and the cycle has four zeros.

0
0
0, 1, 1
0, 1, 1, 2, (0, 2, 2, 1)
0, 1, 1, 2, 3, (0, 3, 3, 1, 4)
0, 1, 1, 2, 3, 5, (0, 5, 5, 2, 7, 1)
0, 1, 1, 2, 3, 5, 8, (0, 8, 8, 3, 11, 1, 12)
0, 1, 1, 2, 3, 5, 8, 13, (0, 13, 13, 5, 18, 2, 20, 1)
0, 1, 1, 2, 3, 5, 8, 13, 21, (0, 21, 21, 8, 29, 3, 32, 1, 33)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, (0, 34, 34, 13, 47, 5, 52, 2, 54, 1)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, (0, 55, 55, 21, 76, 8, 84, 3, 87, 1, 88)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, (0, 89, 89, 34, 123, 13, 136, 5, 141, 2, 143, 1)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657

---

Pisano periods of Lucas numbers If n = L(2 k) ( k ≥ 1), then π( n) = 8 k; if n = L(2 k + 1) ( k ≥ 1), then π( n) = 4 k + 2. That is, if the modulo base is a Lucas number (≥ 3) with an even index, the period is four times the index. If the base is a Lucas number (≥ 4) with an odd index, the period is twice the index.

0
0, 1, (1, 2)
0, 1, 1, (2, 3, 1)
0, 1, 1, 2, (3, 5, 1, 6)
0, 1, 1, 2, 3, (5, 8, 2, 10, 1)
0, 1, 1, 2, 3, 5, (8, 13, 3, 16, 1, 17)
0, 1, 1, 2, 3, 5, 8, (13, 21, 5, 26, 2, 28, 1)
0, 1, 1, 2, 3, 5, 8, 13, (21, 34, 8, 42, 3, 45, 1, 46)
0, 1, 1, 2, 3, 5, 8, 13, 21, (34, 55, 13, 68, 5, 73, 2, 75, 1)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, (55, 89, 21, 110, 8, 118, 3, 121, 1, 122)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, (89, 144, 34, 178, 13, 191, 5, 196, 2, 198, 1)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, (144, 233, 55, 288, 21, 309, 8, 317, 3, 320, 1, 321)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657

For even k, the cycle has two zeros. For odd k, the cycle has only one zero, and the second half of the cycle, which is of course equal to the part on the left of 0, consists of alternatingly numbers F(2 m + 1) and n −  F(2 m), with m decreasing.

---

Number of zeros in the cycle The number of occurrences of 0 per cycle is 1, 2, or 4. Let p be the number after the first 0 after the combination 0, 1. Let the distance between the 0s be q.

• There is one 0 in a cycle, obviously, if p = 1. This is only possible if q is even or n is 1 or 2.
• Otherwise there are two 0s in a cycle if p² ≡ 1. This is only possible if q is even.
• Otherwise there are four 0s in a cycle. This is the case if q is odd and n is not 1 or 2.

For generalized Fibonacci sequences (satisfying the same recurrence relation, but with other initial values, e.g. the Lucas numbers) the number of occurrences of 0 per cycle is 0, 1, 2, or 4.

The ratio of the Pisano period of n and the number of zeros modulo n in the cycle gives the rank of apparition or Fibonacci entry point of n. That is, smallest index k such that n divides F( k). They are:

1, 3, 4, 6, 5, 12, 8, 6, 12, 15, 10, 12, 7, 24, 20, 12, 9, 12, 18, 30, 8, 30, 24, 12, 25, 21, 36, 24, 14, 60, 30, 24, 20, 9, 40, 12, 19, 18, 28, 30, 20, 24, 44, 30, 60, 24, 16, 12, ...

In Renault's paper the number of zeros is called the "order" of F mod m, denoted $\backslash omega(m)$, and the "rank of apparition" is called the "rank" and denoted $\backslash alpha(m)$.

According to Wall's conjecture, $\backslash alpha(p^e)\; =\; p^\{e-1\}\; \backslash alpha(p)$. If $m$ has prime factorization $m\; =\; p\_1^\{e\_1\}\; p\_2^\{e\_2\}\; \backslash dots\; p\_n^\{e\_n\}$ then $\backslash alpha(m)\; =\; \backslash operatorname\{lcm\}(\backslash alpha(p\_1^\{e\_1\}),\; \backslash alpha(p\_2^\{e\_2\}),\; \backslash dots,\; \backslash alpha(p\_n^\{e\_n\}))$.

---

Generalizations The Pisano periods of are

1, 3, 8, 6, 4, 24, 16, 12, 24, 12, 10, 24, 28, 48, 8, 24, 36, 24, 18, 12, 16, 30, 48, 24, 20, 84, 72, 48, 14, 24, 30, 48, 40, 36, 16, 24, 76, 18, 56, 12, 40, 48, 88, 30, 24, 48, 32, ...

The Pisano periods of (or 2-Fibonacci numbers) are

1, 2, 8, 4, 12, 8, 6, 8, 24, 12, 24, 8, 28, 6, 24, 16, 16, 24, 40, 12, 24, 24, 22, 8, 60, 28, 72, 12, 20, 24, 30, 32, 24, 16, 12, 24, 76, 40, 56, 24, 10, 24, 88, 24, 24, 22, 46, 16, ...

The Pisano periods of 3-Fibonacci numbers are

1, 3, 2, 6, 12, 6, 16, 12, 6, 12, 8, 6, 52, 48, 12, 24, 16, 6, 40, 12, 16, 24, 22, 12, 60, 156, 18, 48, 28, 12, 64, 48, 8, 48, 48, 6, 76, 120, 52, 12, 28, 48, 42, 24, 12, 66, 96, 24, ...

The Pisano periods of Jacobsthal numbers (or (1,2)-Fibonacci numbers) are

1, 1, 6, 2, 4, 6, 6, 2, 18, 4, 10, 6, 12, 6, 12, 2, 8, 18, 18, 4, 6, 10, 22, 6, 20, 12, 54, 6, 28, 12, 10, 2, 30, 8, 12, 18, 36, 18, 12, 4, 20, 6, 14, 10, 36, 22, 46, 6, ...

The Pisano periods of (1,3)-Fibonacci numbers are

1, 3, 1, 6, 24, 3, 24, 6, 3, 24, 120, 6, 156, 24, 24, 12, 16, 3, 90, 24, 24, 120, 22, 6, 120, 156, 9, 24, 28, 24, 240, 24, 120, 48, 24, 6, 171, 90, 156, 24, 336, 24, 42, 120, 24, 66, 736, 12, ...

The Pisano periods of Tribonacci numbers (or 3-step Fibonacci numbers) are

1, 4, 13, 8, 31, 52, 48, 16, 39, 124, 110, 104, 168, 48, 403, 32, 96, 156, 360, 248, 624, 220, 553, 208, 155, 168, 117, 48, 140, 1612, 331, 64, 1430, 96, 1488, 312, 469, 360, 2184, 496, 560, 624, 308, 440, 1209, 2212, 46, 416, ...

The Pisano periods of Tetranacci numbers (or 4-step Fibonacci numbers) are

1, 5, 26, 10, 312, 130, 342, 20, 78, 1560, 120, 130, 84, 1710, 312, 40, 4912, 390, 6858, 1560, 4446, 120, 12166, 260, 1560, 420, 234, 1710, 280, 1560, 61568, 80, 1560, 24560, 17784, 390, 1368, 34290, 1092, 1560, 240, 22230, 162800, 120, 312, 60830, 103822, 520, ...

See also generalizations of Fibonacci numbers.

---

Number theory Pisano periods can be analyzed using algebraic number theory.

Let $\backslash pi\_k(n)$ be the n-th Pisano period of the k-Fibonacci sequence F _k( n) ( k can be any natural number, these sequences are defined as F _k(0) = 0, F _k(1) = 1, and for any natural number n > 1, F _k( n) = kF _k( n−1) + F _k( n−2)). If m and n are coprime, then $\backslash pi\_k(m\backslash cdot\; n)\; =\; \backslash mathrm\{lcm\}(\backslash pi\_k(m),\backslash pi\_k(n))$, by the Chinese remainder theorem: two numbers are congruent modulo mn if and only if they are congruent modulo m and modulo n, assuming these latter are coprime. For example, $\backslash pi\_1(3)=8$ and $\backslash pi\_1(4)=6,$ so $\backslash pi\_1(12=3\backslash cdot\; 4)\; =\; \backslash mathrm\{lcm\}(\backslash pi\_1(3),\backslash pi\_1(4))=\; \backslash mathrm\{lcm\}(8,6)=24.$ Thus it suffices to compute Pisano periods for $q=p^n.$ (Usually, $\backslash pi\_k(p^n)\; =\; p^\{n-1\}\backslash cdot\; \backslash pi\_k(p)$, unless p is k-Wall–Sun–Sun prime, or k-Fibonacci–Wieferich prime, that is, p² divides F _k( p − 1) or F _k( p + 1), where F _k is the k-Fibonacci sequence, for example, 241 is a 3-Wall–Sun–Sun prime, since 241² divides F₃(242).)

For prime numbers p, these can be analyzed by using Binet's formula:

$F\_k\backslash left(n\backslash right)\; =\; \}=\; \backslash over\; \{\backslash sqrt\; \{k^2+4\}\}\},\backslash ,$ where $\backslash varphi\_k$ is the kth metallic mean

$\backslash varphi\_k\; =\; \backslash frac\{k\; +\; \backslash sqrt\{k^2+4\}\}\{2\}.$

If k² + 4 is a quadratic residue modulo p (where p > 2 and p does not divide k² + 4), then $\backslash sqrt\{k^2+4\},\; 1/2,$ and $k/\backslash sqrt\{k^2+4\}$ can be expressed as integers modulo p, and thus Binet's formula can be expressed over integers modulo p, and thus the Pisano period divides the totient $\backslash phi(p)=p-1$, since any power (such as $\backslash varphi\_k^n$) has period dividing $\backslash phi(p),$ as this is the order of the group of units modulo p.

For k = 1, this first occurs for p = 11, where 4² = 16 ≡ 5 (mod 11) and 2 · 6 = 12 ≡ 1 (mod 11) and 4 · 3 = 12 ≡ 1 (mod 11) so 4 = , 6 = 1/2 and 1/ = 3, yielding φ = (1 + 4) · 6 = 30 ≡ 8 (mod 11) and the congruence

$F\_1\backslash left(n\backslash right)\; \backslash equiv\; 3\backslash cdot\; \backslash left(8^n\; -\; 4^n\backslash right)\; \backslash pmod\{11\}.$

Another example, which shows that the period can properly divide p − 1, is π₁(29) = 14.

If k² + 4 is not a quadratic residue modulo p, then Binet's formula is instead defined over the quadratic extension field $(\backslash mathbb\{Z\}/p)\backslash sqrt\{k^2+4\}$, which has p² elements and whose group of units thus has order p² − 1, and thus the Pisano period divides p² − 1. For example, for p = 3 one has π₁(3) = 8 which equals 3² − 1 = 8; for p = 7, one has π₁(7) = 16, which properly divides 7² − 1 = 48.

This analysis fails for p = 2 and p is a divisor of the squarefree part of k² + 4, since in these cases are , so one must be careful in interpreting 1/2 or $\backslash sqrt\{k^2+4\}$. For p = 2, is congruent to 1 mod 2 (for k odd), but the Pisano period is not p − 1 = 1, but rather 3 (in fact, this is also 3 for even k). For p divides the squarefree part of k² + 4, the Pisano period is π _k( k² + 4) = p² −  p = p( p − 1), which does not divide p − 1 or p² − 1.

---

Fibonacci integer sequences modulo n One can consider Fibonacci integer sequences and take them modulo n, or put differently, consider Fibonacci sequences in the ring cyclic group. The period is a divisor of π( n). The number of occurrences of 0 per cycle is 0, 1, 2, or 4. If n is not a prime the cycles include those that are multiples of the cycles for the divisors. For example, for n = 10 the extra cycles include those for n = 2 multiplied by 5, and for n = 5 multiplied by 2.

Table of the extra cycles: (the original Fibonacci cycles are excluded) (using X and E for ten and eleven, respectively)

1
2
2
4
3
4
4
8
5
6
14
10

Number of Fibonacci integer cycles mod n are:

1, 2, 2, 4, 3, 4, 4, 8, 5, 6, 14, 10, 7, 8, 12, 16, 9, 16, 22, 16, 29, 28, 12, 30, 13, 14, 14, 22, 63, 24, 34, 32, 39, 34, 30, 58, 19, 86, 32, 52, 43, 58, 22, 78, 39, 46, 70, 102, ...

---

Notes

---

External links

• The Fibonacci sequence modulo m
• A research for Fibonacci numbers
• Fibonacci sequence starts with q, r modulo m
• , a video with Dr. James Grime and the University of Nottingham

Post Comment